import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {

    }
}
class Solution2 {
    //dp[0]=1,dp[1]=1
    //dp[i] += dp[j-1]*dp[i-j]
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0]=dp[1]=1;
        for(int i=2; i<n+1; i++){
            for(int j=1; j<=i; j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
class Solution1 {
    public int maxDistToClosest(int[] seats) {
        int j=0;
        int max = 0;
        for(int i=0; i<seats.length; i++){
            if(seats[i]==1){
                if(j==0 && seats[0]==0)
                    max = i-j;
                else
                    max = Math.max(max,(i-j)/2);
                j=i;
            }
        }
        if(j != seats.length-1){
            return Math.max(max,seats.length-1-j);
        }
        return max;
    }
}
class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int[] ans = new int[queries.length];
        int[] nums = new int[n+1];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<edges.length; i++){
            int x=edges[i][0], y=edges[i][1];
            if(x > y){
                int tmp = x;
                x = y;
                y = tmp;
            }
            nums[x]++;
            nums[y]++;
            map.put(x*(n+1)+y,map.getOrDefault(x*(n+1)+y,0)+1);
            //使的每一个线都是唯一的，如果不唯一就记录有几个重复的线
        }
        int[] arr = Arrays.copyOf(nums,n+1);
        Arrays.sort(arr);
        for(int i=0; i<queries.length; i++){
            int bound=queries[i], total=0;
            for(int a=1,b=n; a<n+1; a++){
                while(b>a && arr[a]+arr[b]>bound){
                    b--;
                }
                total +=n-Math.max(a,b);//统计算上重复的共有几个
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int val = entry.getKey(), freq = entry.getValue();
                int x = val/(n+1), y = val%(n+1);//得到x,y下标
                //如果x,y符合在total中，但是减去重复的线后<=bound,说明不符合条件，total--
                if (nums[x]+nums[y]>bound&&nums[x]+nums[y]-freq <= bound) {
                    total--;
                }
            }
            ans[i] = total;
        }
        return ans;
    }
}
